#ifndef MSC_RBTREE_H
#define MSC_RBTREE_H

#include <stddef.h>
#include <stdbool.h>

//rbtree
//特性：
//(1) 每个节点或者是黑色，或者是红色。
//(2) 根节点是黑色。
//(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
//(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
//(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

#define msc_rbtree_key_sizebit  (sizeof(size_t)*8-1)

#define MS_RBTREE_RED	1
#define MS_RBTREE_BLACK 0

typedef struct ms_rbtree_n {
    struct ms_rbtree_n* parent;
    struct ms_rbtree_n* left;
    struct ms_rbtree_n* right;
    size_t color : 1;
    size_t key : msc_rbtree_key_sizebit;
} *ms_rbtree_p;

#define MS_RBTREE_INIT(t) \
    (t)->parent = (t)->left = (t)->right = t; t->key = 0; t->color = MS_RBTREE_BLACK

#define MS_RBTREE_EMPTY(t) ((t)->parent == t)

#define MS_RBTREE_SIZE(t) ((t)->key)

static inline ms_rbtree_p ms_rbtree_minimum(ms_rbtree_p t, ms_rbtree_p n) {
	while (n->left != t) {
		n = n->left;
	}
    return n;
}
static inline ms_rbtree_p ms_rbtree_maximum(ms_rbtree_p t, ms_rbtree_p n) {
    while (n->right != t)
        n = n->right;
    return n;
}

#define MS_RBTREE_NODE(t)   ((ms_rbtree_p)(t))
#define MS_RBTREE_TOP(t) ((t)->parent != t ? (t)->parent:(t))
#define MS_RBTREE_MINIMUM(t, n) ms_rbtree_minimum((ms_rbtree_p)(t), (ms_rbtree_p)(n))
#define MS_RBTREE_MAXIMUM(t, n) ms_rbtree_maximum((ms_rbtree_p)(t), (ms_rbtree_p)(n))

//左旋：变为右节点的左子节点。右节点变为父节点，当前节点变为右节点的左子节点
static inline void ms_rbtree_rotate_left(ms_rbtree_p t, ms_rbtree_p node) {
    ms_rbtree_p p = node->right; //右节点变为父节点
    p->parent = node->parent;
    //改变父节点
    if (node->parent == t) {
        t->parent = p;
    }
    else {
        if (node == node->parent->left) {
            node->parent->left = p; //如果node是它父节点的左孩子，则将右节点设为该父节点的左孩子
        }
        else if (node == node->parent->right){
            node->parent->right = p;
        }
    }
    //右节点的左子树变为该节点的右子树
    node->right = p->left;
    if (p->left != t) {
        p->left->parent = node;
    }
    p->left = node;
    node->parent = p;
}
#define MS_RBTREE_ROTATE_LEFT(t, n) ms_rbtree_rotate_left((ms_rbtree_p)(t), (ms_rbtree_p)(n))


//右旋：变为左节点的右子节点。左节点变为父节点，当前节点变为左节点的右子节点
static inline void ms_rbtree_rotate_right(ms_rbtree_p t, ms_rbtree_p node) {
    ms_rbtree_p p = node->left; //左节点变为父节点
    p->parent = node->parent;
    //改变父节点
    if (node->parent == t) {
        t->parent = p;
    }
    else {
        if (node == node->parent->left) {
            node->parent->left = p; //如果node是它父节点的左孩子，则将左节点设为该父节点的左孩子
        }
        else {
            node->parent->right = p;
        }
    }
    //左节点的右子树变为该节点的左子树
    node->left = p->right;
    if (p->right != t) {
        p->right->parent = node;
    }
    p->right = node;
    node->parent = p;
}
#define MS_RBTREE_ROTATE_RIGHT(t, n)     ms_rbtree_rotate_right((ms_rbtree_p)(t), (ms_rbtree_p)(n))

static inline void ms_rbtree_fixup_i(ms_rbtree_p t, ms_rbtree_p z) {
    while (z->parent != t && z != t && MS_RBTREE_RED == z->parent->color) {
        //父节点为红色，必存在node->parent->parent
        if (z->parent == z->parent->parent->left) {
            //父节点是左子树，调整右子树颜色
            ms_rbtree_p p = z->parent->parent->right; //叔节点
            if (p != t && MS_RBTREE_RED == p->color) {
                //祖父节点的子节点变黑，祖父节点变红
                z->parent->color = MS_RBTREE_BLACK;
                p->color = MS_RBTREE_BLACK;
                z->parent->parent->color = MS_RBTREE_RED;
                z = z->parent->parent; //继续调整祖父
            } else { //叔节点为黑
                if (z == z->parent->right) {
                    //将z提升为父节点
                    z = z->parent;
                    ms_rbtree_rotate_left(t, z); //z变成左节点
                }

                z->parent->color = MS_RBTREE_BLACK;
                z->parent->parent->color = MS_RBTREE_RED;
                ms_rbtree_rotate_right(t, z->parent->parent);
            }
        }else {
            ms_rbtree_p p = z->parent->parent->left; //叔节点
            if (p != t && MS_RBTREE_RED == p->color) {
                //祖父节点的子节点变黑，祖父节点变红
                z->parent->color = MS_RBTREE_BLACK;
                p->color = MS_RBTREE_BLACK;
                z->parent->parent->color = MS_RBTREE_RED;
                //继续调整祖父
                z = z->parent->parent;
            } else {
                if (z == z->parent->left) {
                    z = z->parent;
                    ms_rbtree_rotate_right(t, z);
                }

                z->parent->color = MS_RBTREE_BLACK;
                z->parent->parent->color = MS_RBTREE_RED;
                ms_rbtree_rotate_left(t, z->parent->parent);
            }
        }
    }
    t->parent->color = MS_RBTREE_BLACK;
}
//插入节点，成功返回根节点
static inline bool ms_rbtree_insert(ms_rbtree_p t, ms_rbtree_p n, bool bMulti) {
    if (NULL == t || NULL == n || t == n) {
        return false;
    }
    ms_rbtree_p p = MS_RBTREE_TOP(t);
    if (p == t) {
        t->parent = n;
        n->left = n->right = t;
        n->parent = t;
        n->color = MS_RBTREE_BLACK;
        ++t->key;
        return true;
    }
    ms_rbtree_p trynode = MS_RBTREE_TOP(t);
    bool _addleft = false;
    if (bMulti) {
        //允许重复
        while (trynode != t) {
            p = trynode;
            if (n->key < trynode->key) { //如果有重复的放在最右边
                trynode = trynode->left;
                _addleft = true;
            }
            else {
                trynode = trynode->right;
                _addleft = false;
            }
        }
    }
    else {
        //不允许重复
        while (trynode != t) {
            p = trynode;
            if (n->key < trynode->key) { //如果有重复的放在最右边
                trynode = trynode->left;
                _addleft = true;
            }
            else {
                if (n->key == trynode->key) {
                    //重复
                    return false;

                }
                trynode = trynode->right;
                _addleft = false;
            }
        }
    }
    n->parent = p;
    n->color = MS_RBTREE_RED;
    if (_addleft) {
        p->left = n;
    }
    else {
        p->right = n;
    }
    n->left = n->right = t;
    ++t->key;
    //修正调整
    ms_rbtree_fixup_i(t,n);
    return true;
}

#define MS_RBTREE_INSERT(t, n ,m)  ms_rbtree_insert((ms_rbtree_p)(t), (ms_rbtree_p)(n), (bool)(m))

// 查询结点前驱节点
static inline ms_rbtree_p ms_rbtree_predecessor(ms_rbtree_p t, ms_rbtree_p node) {
#ifdef _IF_NULL_
    if (node && node != t) {
#endif
    ms_rbtree_p p = t;
    if (node->left != t) {
        p = ms_rbtree_maximum(t, node->left);  // 拥有左子树，后继一定是左子树的最大节点
    } else {
        p = node->parent;
        while(p != t && p->left == node) {  // 找到高层节点中以p所在的树为右子树的树的根节点，即是前驱节点
            node = p;
            p = p->parent;
        }
    }
    return p;
#ifdef _IF_NULL_
    }
    return node;
#endif
}

#define MS_RBTREE_PREDECESSOR(t, n) ms_rbtree_predecessor((ms_rbtree_p)(t), (ms_rbtree_p)(n))

// 查找结点后继节点
static inline ms_rbtree_p ms_rbtree_successor(ms_rbtree_p t, ms_rbtree_p node) {
#ifdef _IF_NULL_
    if (node && node != t) {
#endif
    ms_rbtree_p p = node->parent;
    if (node->right != t) {
        p = ms_rbtree_minimum(t, node->right);  // 拥有右子树，后继一定是右子树的最小节点
    } else {
        while(p != t && p->right == node) {  // 找到高层节点中以p所在的树为左子树的树的根节点，即是后继节点
            node = p;
            p = p->parent;
        }
    }
    return p;
#ifdef _IF_NULL_
    }
    return node;
#endif
}

#define MS_RBTREE_SUCCESSOR(t,n)  ms_rbtree_successor((ms_rbtree_p)(t), (ms_rbtree_p)(n))

//查询节点
static inline ms_rbtree_p ms_rbtree_find(ms_rbtree_p t, size_t key) {
    ms_rbtree_p node = MS_RBTREE_TOP(t);
    while (node != t) {
        if (key < node->key) {
            node = node->left;
        }
        else if (node->key < key){
            node = node->right;
        }
        else {
            return node;
        }
    }
    return t;
}

#define MS_RBTREE_FIND(t, key)  ms_rbtree_find((ms_rbtree_p)(t), (size_t)(key))

static inline void ms_rbtree_fixup_d(ms_rbtree_p t, ms_rbtree_p x) {
    while ((x != t) && (x != t->parent) && (MS_RBTREE_BLACK == x->color)) { //如果当前节点是红色直接变成黑色即可保持特性5成立
        //经过x的路径少一个黑色
        if (x == x->parent->left) { //当前为左节点
            ms_rbtree_p w= x->parent->right; //兄弟节点
            if (MS_RBTREE_RED == w->color) { //红色兄弟节点
                w->color = MS_RBTREE_BLACK;
                x->parent->color = MS_RBTREE_RED; //父节点变成红色
                ms_rbtree_rotate_left(t, x->parent);//w变成祖父节点
                w = x->parent->right; //重新选择x的兄弟节点
            }

            if ((w->left->color == MS_RBTREE_BLACK) && (w->right->color == MS_RBTREE_BLACK)) {
                w->color = MS_RBTREE_RED;
                x = x->parent;
            } else {

                if (w->right->color == MS_RBTREE_BLACK) {
                    w->left->color = MS_RBTREE_BLACK;
                    w->color = MS_RBTREE_RED;
                    ms_rbtree_rotate_right(t, w);
                    w = x->parent->right;
                }

                w->color = x->parent->color;
                x->parent->color = MS_RBTREE_BLACK;
                w->right->color = MS_RBTREE_BLACK;
                ms_rbtree_rotate_left(t, x->parent);
                x = MS_RBTREE_TOP(t);
            }

        } else {

            ms_rbtree_p w = x->parent->left;
            if (w->color == MS_RBTREE_RED) {
                w->color = MS_RBTREE_BLACK;
                x->parent->color = MS_RBTREE_RED;
                ms_rbtree_rotate_right(t, x->parent);
                w = x->parent->left;
            }

            if ((w->left->color == MS_RBTREE_BLACK) && (w->right->color == MS_RBTREE_BLACK)) {
                w->color = MS_RBTREE_RED;
                x = x->parent;
            } else {

                if (w->left->color == MS_RBTREE_BLACK) {
                    w->right->color = MS_RBTREE_BLACK;
                    w->color = MS_RBTREE_RED;
                    ms_rbtree_rotate_left(t, w);
                    w = x->parent->left;
                }

                w->color = x->parent->color;
                x->parent->color = MS_RBTREE_BLACK;
                w->left->color = MS_RBTREE_BLACK;
                ms_rbtree_rotate_right(t, x->parent);
                x = MS_RBTREE_TOP(t);
            }
        }
    }

    x->color = MS_RBTREE_BLACK;
}

//删除一个节点，总共分三种情况
// 1.被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。
// 2.被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。
// 3.被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；
//之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给"被删除节点"之后，再将后继节点删除。
//这样就巧妙的将问题转换为"删除后继节点"的情况了，下面就考虑后继节点。 在"被删除节点"有两个非空子节点的情况下，它的后继节点不可能是双子非空。
//既然"它的后继节点"不可能双子都非空，就意味着"该节点的后继节点"要么没有子节点，要么只有一个子节点。
//若没有子节点，则按"情况① "进行处理；若只有一个子节点，则按"情况② "进行处理。
//参考资料：https://www.cnblogs.com/gcheeze/p/11186806.html
static inline void ms_rbtree_remove(ms_rbtree_p t, ms_rbtree_p node) {
#ifdef _IF_NULL_
    if (node) {
#endif
    if (node == t) return;
    ms_rbtree_p d = t; //顶替删除节点
    ms_rbtree_p x = t; //调整节点
    //node
    if ((node->left == t) || (node->right == t)) {
        d = node; //情况1或2
    } else {
        d = ms_rbtree_successor(t, node); //情况3
    }
    if (d->left != t) {
        x = d->left; //树中删除除位置
		d->left = t;
    } else if (d->right != t) {
        x = d->right;   //树中删除除位置
		d->right = t;
    }
	--t->key; //删除node
    if (x != t) { //x转移到d，相当于删掉x位置
        x->parent = d->parent; //子节点顶替父节点
		if (d->parent == t) {
			t->parent = x; //删除节点是跟节点，则重置根节点
		}
		else if (d == d->parent->left) {
			d->parent->left = x;
		}
		else {
			d->parent->right = x;
		}
		//x->left = x->right = t;
        x->color = d->color;   
		x = t; //删除的是红色节点，全树平衡
    }
    else { //没有x，直接删除d位置
		if (d == t->parent) {
			//顶点
			t->parent = t;
			t->key = 0;
			return;
		}
		x = d;
    }
	//改动了黑色节点
    if (x != t) {
		//经过x的子树黑色节点少1
		//因此兄弟节点的子树节点也要减1
		ms_rbtree_fixup_d(t, x);
		//删除x
		if (x == x->parent->left) {
			x->parent->left = t;
		}
		else if (x == x->parent->right) {
			x->parent->right = t;
		}
	}
    if (d != node) {
        //d顶替node
        d->parent = node->parent;
        if (node->parent == t) {
            t->parent = d;
        }
        else if (node == node->parent->left) {
            node->parent->left = d;
        }
        else {
            node->parent->right = d;
        }
        if (node->left != d) {
            d->left = node->left;
            if (node->left != t) {
                node->left->parent = d;
            }
        }
        else
            d->left = t;
        if (node->right != d) {
            d->right = node->right;
            if (node->right != t) {
                node->right->parent = d;
            }
        }
        else
            d->right = t;
        d->color = node->color;
    }
#ifdef _IF_NULL_
	}
#endif
}

#define MS_RBTREE_REMOVE(t,n) ms_rbtree_remove((ms_rbtree_p)(t), (ms_rbtree_p)(n))

//not less than key
static inline ms_rbtree_p ms_rbtree_lower_bound(ms_rbtree_p t, size_t key) {
    ms_rbtree_p node = MS_RBTREE_TOP(t);
    ms_rbtree_p p = t;
    while (node != t) {
        if (node->key < key) {
            node = node->right;
        }
        else {
            p = node;
            node = node->left;
        }
    }
    return p;
}
#define MS_RBTREE_LOWER_BOUND(t, key) ms_rbtree_lower_bound((ms_rbtree_p)(t), (size_t)(key))
//greater than key
static inline ms_rbtree_p ms_rbtree_upper_bound(ms_rbtree_p t, size_t key) {
    ms_rbtree_p node = MS_RBTREE_TOP(t);
    ms_rbtree_p p = t;
    while (node != t) {
        if (key < node->key) {
            p = node;
            node = node->left;
        }
        else {
            node = node->right;
        }
    }
    return p;
}
#define MS_RBTREE_UPPER_BOUND(t, key)   ms_rbtree_upper_bound((ms_rbtree_p)(t), (size_t)(key))

static inline ms_rbtree_p ms_rbtree_begin(ms_rbtree_p t) {
    return ms_rbtree_minimum(t, MS_RBTREE_TOP(t));
}
#define MS_RBTREE_BEGIN(t) ms_rbtree_begin((ms_rbtree_p)(t))
static inline ms_rbtree_p ms_rbtree_next(ms_rbtree_p t, ms_rbtree_p node) {
    return ms_rbtree_successor(t, node);
}
#define MS_RBTREE_NEXT(t, n) ms_rbtree_next((ms_rbtree_p)(t), (ms_rbtree_p)(n))
static inline ms_rbtree_p ms_rbtree_end(ms_rbtree_p t) {
    return t;
}
#define MS_RBTREE_END(t) ((ms_rbtree_p)(t))
static inline ms_rbtree_p ms_rbtree_rbegin(ms_rbtree_p t) {
    return ms_rbtree_maximum(t, MS_RBTREE_TOP(t));
}
#define MS_RBTREE_RBEGIN(t) ms_rbtree_rbegin((ms_rbtree_p)(t))
static inline ms_rbtree_p ms_rbtree_rnext(ms_rbtree_p t, ms_rbtree_p node) {
    return ms_rbtree_predecessor(t, node);
}
#define MS_RBTREE_RNEXT(t, n) ms_rbtree_rnext((ms_rbtree_p)(t), (ms_rbtree_p)(n))
static inline ms_rbtree_p ms_rbtree_rend(ms_rbtree_p t) {
    return t;
}
#define MS_RBTREE_REND ((ms_rbtree_p)(t))
#endif // MSC_RBTREE_H
